package com.cheung.leetcode.arr;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.arr
 * @Author :  cheungming
 * @CreateTime : 2024-08-16 18:57:32
 * @Description : 15
 * @Version : 1.0
 */
public class Code15Test {

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        if (nums[0] > 0) {
            return new ArrayList<>();
        }
        // 设 a,b,c 是要求的三个数
        // first ,second,third 是三个索引
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        // 遍历a，即nums[first],则b+c的和为-a,也就是nums[second] + nums[third] = -nums[first]
        for (int first = 0; first < n; first++) {
            // 相同的数跳过
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c初始化为数组末尾
            int third = n - 1;
            // b+c的和为-a，即nums[second] + nums[third] = -nums[first]
            int target = -nums[first];
            // 遍历b，即nums[second]
            for (int second = first + 1; second < n; second++) {
                // 相同的数跳过
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }

                // second必须小于third
                while (second < third && nums[second] + nums[third] > target) {
                    third--;
                }

                if (second == third) {
                    break;
                }

                // 找到满足条件的三个数
                if (nums[second] + nums[third] == target) {
                    result.add(List.of(nums[first], nums[second], nums[third]));
                }
            }
        }

        return result;
    }


    @Test
    public void test1() {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists1 = List.of(List.of(-1, 0, 1), List.of(-1, -1, 2));
        List<List<Integer>> lists2 = List.of(List.of(-1, -1, 2), List.of(-1, 0, 1));

        assert threeSum(nums).equals(lists1) || threeSum(nums).equals(lists2);
    }

    @Test
    public void test3() {
        int[] nums = {0, 1, 1};
        assert threeSum(nums).isEmpty();
    }
}
